package likou;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/12/08 08:46
 */
public class _689 {
    public static void main(String[] args) {
        _689 one = new _689();
        System.out.println(Arrays.toString(one.maxSumOfThreeSubarraysB(new int[]
                        {20, 8, 16, 16, 9, 7, 13, 3, 1, 16, 5, 17, 6, 14, 20, 20, 3, 14, 19, 16, 4, 15, 11, 11, 11, 14, 20, 6, 6, 1, 19, 16, 6, 3, 4, 11, 14, 5, 14, 13, 5, 6, 1, 8, 13, 17, 11, 7, 7, 14, 20, 14, 11, 20, 13, 20, 15, 19, 17, 2, 17, 1, 2, 3, 16, 9, 3, 15, 15, 9, 8, 12, 7, 10, 2, 9, 6, 6, 19, 2, 3, 11, 10, 12, 13, 5, 8, 2, 13, 4, 2, 7, 12, 5, 12, 4, 14, 2, 4, 6}
                , 8)));
    }

    int[] res = new int[3];
    int max = 0;

    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int len = nums.length;
        int[] numsa = new int[len];
        int now = 0, index = 0;
        while (index < k) {
            now += nums[index++];
        }
        numsa[index - 1] = now;
        for (; index < len; index++) {
            numsa[index] = numsa[index - 1] - nums[index - k] + nums[index];
        }
        dfs(numsa, k - 1, 0, 0, new int[3], k);
        for (int i = 0; i < 3; i++) {
            res[i] = res[i] - k + 1;
        }
        return res;
    }

    public void dfs(int[] numsa, int i, int now, int p, int[] nowRes, int k) {
        if (p == 3) {
            if (now > max) {
                System.arraycopy(nowRes, 0, res, 0, 3);
                max = now;
            }
            return;
        }
        int len = numsa.length - (2 - p) * k;
        for (; i < numsa.length && i < len; i++) {
            nowRes[p] = i;
            dfs(numsa, i + k, now + numsa[i], p + 1, nowRes, k);
        }
    }


    public static int[] maxSumOfThreeSubarraysB(int[] nums, int k) {
        int N = nums.length;

        //从左边遍历
        int[] range = new int[N]; //以i位置结尾的子数组之和
        int[] left = new int[N];  // i位置及之前：和最大的子数组的结尾下标

        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        range[k - 1] = sum;
        left[k - 1] = k - 1;

        int max = sum;
        for (int i = k; i < N; i++) { //从左边遍历数组
            sum = sum - nums[i - k] + nums[i]; //子数组之和
            range[i] = sum; // 存放到range数组

            // 处理left
            left[i] = left[i - 1];//假设和最大的数组没变
            if (sum > max) {//变了。小于号保证字典序
                max = sum;
                left[i] = i;
            }
        }

        //从右边遍历
        sum = 0;
        for (int i = N - 1; i >= N - k; i--) {
            sum += nums[i];
        }
        max = sum;
        int[] right = new int[N]; //i及i之后：和最大的子数组开始下标
        right[N - k] = N - k; //最后一个数组 N-k到N-1
        for (int i = N - k - 1; i >= 0; i--) {
            sum = sum - nums[i + k] + nums[i];

            right[i] = right[i + 1];
            if (sum >= max) { //大于等于号保证字典序
                max = sum;
                right[i] = i;
            }
        }

        int a = 0;
        int b = 0;
        int c = 0;
        max = 0;
        // 从中间，往左右，左边的那个是左边最大的，右边那个是右边最大的。
        for (int i = 2 * k - 1; i < N - k; i++) { // 中间一块的起始点 (0...k-1)选不了 i == N-1
            int part1 = range[left[i - k]]; //左边的子数组最大和
            int part2 = range[i]; //中间数组之和
            int part3 = range[right[i + 1] + (k - 1)];//right[i+1]表示第三个子数组（和最大）的开始坐标，
            if (part1 + part2 + part3 > max) {
                max = part1 + part2 + part3;
                a = left[i - k] - (k - 1);
                b = i - (k - 1);
                c = right[i + 1];
            }
        }
        return new int[]{a, b, c};
    }
}
